import java.util.*;

/**
 * Package: PACKAGE_NAME
 * Created by OriKey on 2020/9/2.
 * --- 平凡才是唯一的答案 ---
 */

//该类的方法需要满足多个线程进行调用时不会出现重复计算的问题
//解决思路：构建一个对应的数组list来存储在具体数值的素数个数
//        如果其余线程访问这个函数的时候list[end]>=输入的值，说明需要返回的结果集已经在
//        res中，则返回res.subList(0,list[end])即可实现告诉相应
public class SecondProblem {

    private ArrayList<Integer> list;//用来存储i位置之前的素数个数
    private ArrayList<Integer> res ;//用来存储结果集
    SecondProblem(){
        list = new ArrayList<>();
        list.add(0);//初始化0下标为0
        list.add(0);//初始化1下标为0
        res = new ArrayList<>();
    }
    public synchronized List<Integer> getPrime(int N) {

        //首先判断非法输入
        if (N <= 0) {
            System.out.println("输入非法");
            return null;
        }
        //判断是否已经在计算的结果中了，如果是的话将直接返回
        if (N<list.size()){
            System.out.println("1执行：本处代码被执行，说明返回的是已经被计算的结果，完成目标快速响应");
            return res.subList(0,list.get(N));
        }
        int cur = 2;
        if (N>=list.size()&&list.size()!=2){
            System.out.println("2执行：本处代码被执行，说明本次遍历是从一个较小的输入的N开始，完成目标避免重复计算");
            cur=list.get(list.size()-1);
        }
        //使用筛法判断，但数值过于巨大的时候，我们使用筛法判断
        if (N >= 10000000 && N <= Integer.MAX_VALUE) {
            int n = Long.valueOf(N).intValue();

            boolean[] array;
            try {
                array = new boolean[n];
                for (int i = cur; i < n; i++) {
                    array[i] = true;
                }
                for (int i = cur; i < n; i++) {
                    if (array[i]) {//判断是否是素数
                        int j, temp;
                        temp = i;
                        for (j = 2 * temp; j < n; j = j + temp) {
                            array[j] = false;//把这个数相应的倍数全部标记为非素数
                        }
                        res.add(i);
                        list.add(list.get(list.size()-1)+1);
                    }
                    list.add(list.get(list.size()-1));
                }
            } catch (OutOfMemoryError e) {
                System.out.println("您的空间大小不足，将自动退化到一般解法，可能需要较长时间");
                for (int i = cur; i < N; i++) {
                    if (isPrime(i)) {
                        res.add(i);
                        list.add(list.get(list.size()-1)+1);
                    }
                    list.add(list.get(list.size()-1));
                }
            }

        } else {
            for (int i = 2; i < N; i++) {
                if (isPrime(i)) {
                    try{
                        res.add(i);
                        list.add(list.get(list.size()-1)+1);
                    }catch (Exception e){
                        e.printStackTrace();
                    }
                }else{
                    list.add(list.get(list.size()-1));
                }

            }
        }

        return res;

    }

    //高效判断素数，基于6N原则实现
    private  boolean isPrime(int num) {
        if (num == 2 || num == 3) {
            return true;
        }

        //如果不在6的倍数附近，肯定不是素数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        //对6倍数附近的数进行判断
        for (int i = 5; i <= Math.sqrt(num); i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

}
